﻿// Write a program that sorts an array of strings using the quick sort algorithm (find it in Wikipedia).

using System;

class QuickSort
{
    static void Main(string[] args)
    {
        // get the length of the array
        Console.Write("Enter length of the array : ");
        string length = Console.ReadLine();
        int lengthOfArray;
        while (!int.TryParse(length, out lengthOfArray))
        {
            Console.Write("Invalid input. Enter again length for the array : ");
            length = Console.ReadLine();
        }

        string[] unsorted = new string[lengthOfArray];

        for (int index = 0; index < lengthOfArray; index++)
        {
            // get the element of the array
            Console.Write("Enter element of the array : ");
            string element = Console.ReadLine();
            unsorted[index] = element;
        }

        // Print the unsorted array
        for (int i = 0; i < unsorted.Length; i++)
        {
            Console.Write(unsorted[i] + " ");
        }

        Console.WriteLine();

        // Sort the array
        Quicksort(unsorted, 0, unsorted.Length - 1);

        // Print the sorted array
        for (int i = 0; i < unsorted.Length; i++)
        {
            Console.Write(unsorted[i] + " ");
        }

        Console.WriteLine();
    }

    public static void Quicksort(IComparable[] elements, int left, int right)
    {
        int i = left, j = right;
        IComparable pivot = elements[(left + right) / 2];

        while (i <= j)
        {
            while (elements[i].CompareTo(pivot) < 0)
            {
                i++;
            }

            while (elements[j].CompareTo(pivot) > 0)
            {
                j--;
            }

            if (i <= j)
            {
                // Swap
                IComparable tmp = elements[i];
                elements[i] = elements[j];
                elements[j] = tmp;

                i++;
                j--;
            }
        }

        // Recursive calls
        if (left < j)
        {
            Quicksort(elements, left, j);
        }

        if (i < right)
        {
            Quicksort(elements, i, right);
        }
    }

}
